#ifndef __BASE_STRUCTURE_LINUX_RBTREE_H
#define __BASE_STRUCTURE_LINUX_RBTREE_H

#include <stdio.h>
#include <stddef.h>
/*
  模仿 linux Kernel 设计的红黑树
*/

struct rb_node {
    struct rb_node *parent, *left, *right;
#define RB_RED   0
#define RB_BLACK 1
    unsigned int color;
};

struct rb_root {
    struct rb_node *rb_node;
};

#define RB_ROOT_INIT(root) { NULL, }

#define container_of(ptr, type, member) (                           \
        (type*)((char*)((type*)(ptr)) - offsetof(type, member)) )

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

/* 因为有 while 判断，所以改用宏实现提高性能 */
#define rb_node_add(newnode, root, compare_fn, duplicate_node) do {     \
        struct rb_node ** __link = &(root)->rb_node;                    \
        struct rb_node * __parent = __link[0];                          \
        struct rb_node * __duplicate = NULL;                            \
        int ret ;                                                       \
        while (__link[0])  {                                            \
            __parent = __link[0];                                       \
            ret = (compare_fn)((newnode), __parent);                    \
            if (ret == 0) {                                             \
                __duplicate = __parent;                                 \
                break;                                                  \
            }  else if ( ret < 0 ) {                                    \
                __link = &(__link[0]->left);                            \
            }   else if (ret > 0) {                                     \
                __link = &(__link[0]->right);                           \
            }                                                           \
        }                                                               \
        (duplicate_node) = __duplicate;                                 \
        if (__duplicate == NULL) {                                      \
            rb_node_link(newnode, __parent, __link);                    \
            rb_insert_color(newnode, root);                             \
        }                                                               \
    } while (0)

extern void rb_insert_color(struct rb_node *node, struct rb_root *root);
extern void rb_erase(struct rb_node *node, struct rb_root *root);

static inline void rb_node_link(struct rb_node *newnode,
                                struct rb_node *parent, struct rb_node **link) {
    newnode->parent = parent;
    newnode->left = newnode->right = NULL;
    newnode->color = RB_RED;

    *link = newnode;
}

#define rb_node_find(root, what, compare_fn, res_node) do {     \
        struct rb_node *__n = (root)->rb_node;                  \
        (res_node) = NULL;                                      \
        while (__n) {                                           \
            int __hr = (compare_fn)(what, __n);                 \
            (res_node) = __n;                                   \
            if (__hr == 0) { (res_node) = __n; break; }         \
            else if (__hr < 0) { __n = __n->left; }             \
            else { __n = __n->right; }                          \
        }                                                       \
    }   while (0)


#endif
